package top.hkyzf.study.leetcode.array;

import org.junit.Test;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 朱峰
 * @date 2022-1-29 14:00
 */
class Queen {

	// 八皇后问题，在一个8×8的国际象棋棋盘上摆放8个皇后，摆放需遵守皇后不能处于同一行、同一列、同一斜线上，问有多少种摆法
	int max = 8;//皇后个数
	static  int count = 0;//记录有多少种摆法
	// 初始化一个数组用于存放结果
	/*
	 * 这里用一维数组存放数据就可以了，这里一维数组中的值存放的是皇后的列坐标，
	 * 因为规定皇后是不能摆放在同一行，所以每一行只有一个皇后 ； 一维数组 arr
	 * 的第一个值就是 棋盘第一行皇后的列坐标值，第二个值就是皇后在棋盘第二行的列坐标值
	 */
	int[] arr = new int[max];

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Queen quuen = new Queen();
		quuen.PutQuuen(0);
		System.out.println("共有"+count+"种摆法");
	}

	//写一个摆皇后的方法
	private void PutQuuen(int n) {
		if(n==max) {//因为n是从0开始增加，即n=0表示放第一个皇后，当n==max时表示皇后已经摆完了
			Print();
			return;
		}
		for(int i=0;i<max;i++) {
			arr[n]=i;//放置第一个皇后
			if(judge(n)) {//判断皇后的位置是否冲突，不冲突继续放下一个皇后
				PutQuuen(n+1);
			}
		}
	}


	// 写一个方法，判断皇后在该位置是否会引起冲突，即在同一行或同一列或同一斜线
	private boolean judge(int n) {
		for (int i = 0; i < n; i++) {

			/*
			 * 1. 判断 皇后是否在同一列，只需判断皇后的列坐标是否相等即可，即arr[i] == arr[n]
			 * 2.判断皇后是否在同一斜线上，只需判断两个皇后的列坐标之差的绝对值与其横坐标之差的绝对值是否相等即可，
			 *   即Math.abs(n - i) == Math.abs(arr[i] - arr[n])
			 *  */
			if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[i] - arr[n])) {
				return false;//违反了规则，返回false
			}
		}
		return true;
	}

	//输出
	private void Print() {
		// TODO Auto-generated method stub
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i] + " ");
		}
		count++;
		System.out.println();
	}

}

public class MyQueen {
	private List<List<Integer>> putQueen(int queenNum) {
		int[][] board = new int[queenNum][queenNum];
		List<List<Integer>> result = new LinkedList<>();
		Deque<Integer> trace = new LinkedList<>();
		dfs(board, 0, trace, result);
		return result;
	}

	void dfs(int[][] board, int row, Deque<Integer> trace, List<List<Integer>> result) {
		if (row > board.length-1) {
			result.add(new LinkedList<>(trace));
			return;
		}
		for (int col = 0; col < board.length; col++) {
			if (!check(board, row, col)) {
				continue;
			}
			board[row][col] = 1;
			trace.add(col);
			dfs(board, row + 1, trace, result);
			trace.removeLast();
			board[row][col] = 0;
		}
	}

	/**
	 * 检查是否可以放皇后
	 * @param row 行
	 * @param col 列
	 * @return 返回 true 可放置， false 不可放置
	 */
	boolean check(int[][] board, int row, int col) {
		// 检查列是否冲突
		for (int[] ints : board) {
			if (ints[col] == 1) {
				return false;
			}
		}
		// 检查左上方
		for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
			if (board[i][j] == 1) {
				return false;
			}
		}
		// 金叉右上方
		for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
			if (board[i][j] == 1) {
				return false;
			}
		}
		return true;
	}

	@Test
	public void testPutQueen () {
		int queenNum = 8;
		List<List<Integer>> result = putQueen(queenNum);
		for (List<Integer> integers : result) {
			System.out.println(integers);
		}
		System.out.println(result.size());
	}
}
